﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace TSP
{
    /// <summary>
    /// Rozszerzenie interfejsu IGraph o wyznaczanie minimalnego drzewa rozpinającego algorytmem Kruskala
    /// </summary>
    public static class Kruskal
        {

        /// <summary>
        /// Wyznacza minimalne drzewo rozpinające grafu algorytmem Kruskala
        /// </summary>
        /// <param name="g">Badany graf</param>
        /// <returns>Wyznaczone drzewo rozpinające</returns>
        /// <remarks>
        /// Dla grafu skierowanego metoda zgłasza wyjatek System.ArgumentException.<br/>
        /// Wyznaczone drzewo reprezentowane jast jako graf bez cykli, to umozliwia jednolitą obsługę sytuacji
        /// gdy analizowany graf jest niespójny, wynik jest wówczas lasem rozpinającym.
        /// </remarks>
        public static IGraph KruskalMST(this IGraph g)
            {
            if ( g.Directed ) throw new System.ArgumentException("Directed graphs are not allowed");

            var equiv=new UnionFind(g.VerticesCount);
            var edges=new EdgesMinPriorityQueue();
            int n,f,t;
            Edge me;
            IGraph mst=g.IsolatedVerticesGraph();
            for ( int v=0 ; v<g.VerticesCount ; ++v  )
                foreach ( Edge e in g.OutEdges(v) )
                    if ( e.from<e.to )
                        edges.Put(e);
            n=0;
            while ( n<g.VerticesCount-1 && !edges.Empty )
                {
                me=edges.Get();
                f=equiv.Find(me.from);
                t=equiv.Find(me.to);
                if ( f!=t )
                    {
                    equiv.Union(f,t);
                    mst.AddEdge(me.from,me.to,me.weight);
                    ++n;
                    }    
                }
            return mst;
            }

        }  //  class KruskalGraphExtender

}
    
